package elementaryAlgorithm;


import java.util.ArrayList;
import java.util.List;

/**
 * 104. 二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回它的最大深度 3 。
 * */
public class MaximumDepthOfBinaryTree {

    public static void main(String[] args) {
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
        TreeNode node3 = new TreeNode(20,node4,node5);
        TreeNode node2 = new TreeNode(9);
        TreeNode node1 = new TreeNode(3,node2,node3);
        MaximumDepthOfBinaryTree maximumDepthOfBinaryTree = new MaximumDepthOfBinaryTree();
        int result = maximumDepthOfBinaryTree.maxDepth(node1);
        System.out.println(result);
    }
    public int maxDepth(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        List<Integer> resList = this.preOrder(root, 1, list);
        int result = 0;
        for (int i : resList) {
            if (i > result){
                result = i;
            }
        }
        return result;
    }

    public List<Integer> preOrder(TreeNode node,int parDepth,List<Integer> result){

        if (node == null){
            return result;
        }

        result.add(parDepth);

        preOrder(node.left,parDepth+1 ,result);

        preOrder(node.right,parDepth+1 ,result);

        return result;
    }
}
